Problem :

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1 :

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2 :

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

核心思維 :

1. 取得陣列大小，設置目標為陣列的最後一個位置
2. 從倒數第二個位置向前遍歷，若當前位置可以跳躍到目標，則更新目標為當前位置
3. 若目標位置為起始位置則回傳true，表示可以跳到最後一個位置
4. 若目標位置不為起始位置則回傳false

程式碼 :

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //取得陣列大小
        int n = nums.size();
        //設定目標為陣列最後一個位置
        int target = n -1;
        //從倒數第二個位置向前進行遍歷
        for(int i = n - 1; i > -1; i--){
            //若當前位置的跳躍範圍可以直接到目標位置則更新目標為當前位置
            if(nums[i] + i >= target){
                target = i;
            }
        }
        //若目標位置為起始位置則回傳true
        if(target == 0){
            return true;
        }
        //若目標位置不為起始位置則回傳false
        return false;
    }
};

結論 :

這題的目標是判斷陣列的起始位置跳躍到最後一個位置，透過反向遍歷檢查每個位置的跳躍範圍，若能夠從起始位置抵達最後一個位置則為傳true，若不行則回傳false，時間複雜度為O(n)。